﻿using System;
using System.Collections.Generic;
using Algoritmia.DataStructures.Maps;
using Algoritmia.DataStructures.Queues;

namespace Algoritmia.Utils.Backtracers
{
    public class DynamicBacktracer<T,TResult> : IBacktracer<T,TResult>
    {
        private readonly IMap<T, T> _backpointers;
        private readonly Func<DataStructures.Lists.IList<TResult>> _createList;
        private readonly Func<ILifo<TResult>> _createLifo;

        public DynamicBacktracer(IEnumerable<KeyValuePair<T,T>> backpointers = null, 
                Func<IEnumerable<KeyValuePair<T,T>>, IMap<T,T>> createMap = null,
                Func<DataStructures.Lists.IList<TResult>> createList = null,
                Func<ILifo<TResult>> createLifo = null)
        {
            if (backpointers is IMap<T, T>)
            {
                _backpointers = (IMap<T, T>)backpointers;
            }
            else
            {
                createMap = createMap ?? (it => AlgoritmiaFactory.Maps<T, T>.BuildDefault(it));
                _backpointers = createMap(backpointers);
            }
            _createList = createList ?? (() => AlgoritmiaFactory.Lists<TResult>.Default);
            _createLifo = createLifo ?? (() => AlgoritmiaFactory.Lifos<TResult>.Default);
        }

        #region Implementation of IBacktracer<T>

        public DataStructures.Lists.IList<TResult> Backtrace(T target, Func<T,IMap<T,T>,TResult> selector = null, EqualityComparison<T> equalityComparison = null)
        {
            equalityComparison = AlgoritmiaFactory.GetDefaultEqualityComparison(equalityComparison);
            if ( selector == null )
            {
                if ( typeof(T) != typeof(TResult))
                {
                    throw new ArgumentNullException("selector","the argument should be provided when if T and TResult are different types");
                }
                selector = (e, back) => (TResult) (object) e;
            }
            if (!_backpointers.Contains(target))
            {
                throw new ArgumentException(String.Format("Element {0} is not contained on the backpointers provided", target), "target");
            }
            T aux = target;

            var lifo = _createLifo();

            while (!equalityComparison(_backpointers[aux],aux))
            {
                lifo.Push(selector(aux, _backpointers));
                aux = _backpointers[aux];
            }
            var list = _createList();
            while ( lifo.Count > 0)
            {
                list.Add(lifo.Pop());
            }

            return list;
        }

        #endregion
    }
}
